import com.sun.jmx.snmp.SnmpUnknownMsgProcModelException;
import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/10 15:18
 */
public class 泛型递归_树的递归 {

    /*
    * #problem 22 括号生成
    * */
    // 1. 递归
    public List<String> generateParenthesis(int n) {
        char[] cur = new char[n*2];
        int pos = 0;
        return generate(cur,pos);
    }

    private List<String> generate(char[] cur,int pos) {
        if(cur.length == pos) {
            List<String> res = new ArrayList();
            if(valid(cur)) {
                res.add(new String(cur));
            }
            return res;
        }
        cur[pos] = '(';
        List<String> res = generate(cur,pos+1);
        cur[pos] = ')';
        res.addAll(generate(cur,pos+1));
        return res;
    }

    private boolean valid(char[] cur) {
        int balance = 0;
        for(char c : cur) {
            if(c=='(') {
                balance ++;
            } else {
                balance --;
            }
            if(balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    // 2. 递归-2 ==> 保证序列的正确性
    // left < n ==> 加入 (
    // right < left ==> 加入 )
    public List<String> generateParenthesis1(int n) {
        char[] cur = new char[n*2];
        int pos = 0,left = 0,right=0;
        return generate(cur,pos,left,right);
    }

    private List<String> generate(char[] cur,int pos,int left,int right) {
        if(cur.length == pos) {
            List<String> res = new ArrayList();
            res.add(new String(cur));
            return res;
        }
        List<String> res = new ArrayList();
        int n = cur.length/2;
        if(left < n ) {
            cur[pos] = '(';
            res.addAll(generate(cur,pos+1,left+1,right));
        }
        if(right < left) {
            cur[pos] = ')';
            res.addAll(generate(cur,pos+1,left,right+1));
        }
        return res;
    }

    /*
    * #problem 226 翻转二叉树
    * */
    // 1. 层序遍历
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        Deque<TreeNode> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()) {
            int length = queue.size();
            for(int i=0;i<length;++i) {
                TreeNode cur = queue.removeFirst();
                TreeNode temp = cur.left;
                cur.left = cur.right;
                cur.right = temp;
                if(cur.left != null) {
                    queue.addLast(cur.left);
                }
                if(cur.right != null) {
                    queue.addLast(cur.right);
                }
            }
        }
        return root;
    }

    // 2. 递归
    public TreeNode invertTree2(TreeNode root) {
        if(root == null) {
            return root;
        }
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;
        invertTree2(root.left);
        invertTree2(root.right);
        return root;
    }
    // 3. 递归
    public TreeNode invertTree3(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) {
            return root;
        }
        invertTree3(root.left);
        invertTree3(root.right);
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;
        return root;
    }

    /*
    * #problem 98 验证二叉搜索树
    * 二叉搜索树 --> 左子树的所有值小于 root.val
    *           --> 右子树的所有值大于 root.val
    * */
    // 1. 递归
    public boolean isValidBST(TreeNode root) {
        return validBst(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }
    // root.val 位于 (left,right)区间
    private boolean validBst(TreeNode root,int left,int right) {
        if(root == null) {
            return true;
        }
        if(root.val <= left) {
            return false;
        }
        if(root.val >= right) {
            return false;
        }
        return validBst(root.left,left,root.val) && validBst(root.right,root.val,right);
    }

    // 2. 中序遍历 ==> 二叉搜索树的中序遍历结果为升序数组
    public boolean isValidBST1(TreeNode root) {
        List<Integer> res = f(root);
        for(int i =1;i<res.size();++i) {
            if(res.get(i) < res.get(i-1)) {
                return false;
            }
        }
        return true;
    }

    private List<Integer> f(TreeNode root) {
        if(root == null) {
            return new ArrayList();
        }
        List<Integer> res = f(root.left);
        res.add(root.val);
        res.addAll(f(root.right));
        return res;
    }

    // 3. 中序遍历
    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {
        if(root == null) {
            return true;
        }
        if(!isValidBST2(root.left)) {
            return false;
        }
        if(root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST2(root.right);
    }


    /*
    * #problem 104 二叉树的最大深度
    * 可以使用递归 或者层序遍历
    * */
    // 1. 递归
    public int maxDepth(TreeNode root) {
        if(root == null ) {
            return 0;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        return Math.max(leftH,rightH) + 1;
    }

    // 2.层序遍历
    public int maxDepth1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        int res = 0;
        while(!queue.isEmpty()) {
            int length = queue.size();
            for(int i =0;i<length;++i) {
                TreeNode cur = queue.removeFirst();
                if(cur.left != null) {
                    queue.addLast(cur.left);
                }
                if(cur.right != null) {
                    queue.addLast(cur.right);
                }
            }
            res++;
        }
        return res;
    }

    /*
    * #problem 111 二叉树的最小深度
    * */
    // 1. 递归
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        // 叶子结点
        if(root.left == null && root.right == null) {
            return 1;
        }
        if(root.left == null) {
            return minDepth(root.right) + 1;
        } else if(root.right == null) {
            return minDepth(root.left) + 1;
        } else {
            return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
        }
    }

    // 2. 迭代
    public int minDepth2(TreeNode root) {
        // 第一个叶子节点 ==> 就是最小深度
        int res = 0;
        if(root == null) {
            return res;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()) {
            res++;
            int length = queue.size();
            for(int i =0;i<length;++i) {
                TreeNode cur = queue.removeFirst();
                if(cur.left == null && cur.right == null) {
                    return res;
                }
                if(cur.left != null) {
                    queue.addLast(cur.left);
                }
                if(cur.right != null) {
                    queue.addLast(cur.right);
                }
            }
        }
        return res;
    }

    /*
    * #problem  236 二叉树的最近公共祖先
    * */
    // 1. 递归
    /*
    * 当一个节点的左子树包含p/q ，右子树包含另一个，那么该结点就是p q 的最近公共祖先
    * 因为 p != q ==> 当 p 和q都在某个结点的左/右子树上时，说明当前结点不为最近公共祖先
    * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        // 找到 p/q所在的结点
        if(root.val == p.val || root.val == q.val) {
            return root;
        }
        // 寻找 p/q所在的结点
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        // 当前结点为LCA结点
        if(left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }

    //2. 用map记录祖先
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> parent = new HashMap<>();
        dfs(root,parent);
        // 记录走过的祖先
        Set<TreeNode> visited = new HashSet<>();
        TreeNode parentNode = p;
        while(parentNode != null) {
            visited.add(parentNode);
            parentNode = parent.get(parentNode);
        }
        parentNode = q;
        while(parentNode != null) {
            if(visited.contains(parentNode)) {
                return parentNode;
            }
            parentNode = parent.get(parentNode);
        }
        return null;
    }

    private void dfs(TreeNode root,Map<TreeNode,TreeNode> parent) {
        if(root.left != null) {
            parent.put(root.left,root);
            dfs(root.left,parent);
        }
        if(root.right != null) {
            parent.put(root.right,root);
            dfs(root.right,parent);
        }
    }

    /*
    * #problem 105 从前序与中序遍历序列构造二叉树
    * */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree1(preorder,inorder,0,preorder.length,0);
    }

    private TreeNode buildTree1(int[] preorder,int[] inorder,int left,int right,int pos) {
        if(left >= right) {
            return null;
        }
        // 根节点
        TreeNode root = new TreeNode(preorder[pos]);
        // 在中序数组中找到根结点所在的位置
        int k = -1;
        for(k= left;k<right;k++) {
            if(inorder[k] == root.val) {
                break;
            }
        }
        // 构建左右子树
        TreeNode leftNode = buildTree1(preorder,inorder,left,k,pos+1);
        // k - left ==> 左子树的长度
        TreeNode rightNode = buildTree1(preorder,inorder,k+1,right,pos + k-left +1);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    /*
    * #problem 77 组合
    * */
    // 1. 递归-深搜 ==> 每个位置都会有两种选择 1. 选择当前元素 2. 不选择当前元素
    private List<Integer> temp = new LinkedList<>();
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }

    private void dfs(int n,int k,int cur) {
        if(temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        // 不足以构造出长度为k的序列
        if(temp.size() + (n-cur + 1) < k) {
            return ;
        }
        // 选择当前位置
        temp.add(cur);
        dfs(n,k,cur+1);
        // 回溯，不选择当前位置
        temp.remove(temp.size()-1);
        dfs(n,k,cur+1);
    }

    private void dfs1(int n,int k,int cur) {
        if(temp.size() == k) {
            res.add(temp);
        }
        // 遍历每一种可能
        for(int i = cur;i<=n - (k-temp.size()) + 1;i++) {
            temp.add(i);
            dfs1(n,k,i+1);
            temp.remove(temp.size()-1);
        }
    }

    /*
    * #problem 46 全排列
    * */
    public List<List<Integer>> permute(int[] nums) {
        int length = nums.length;
        boolean[] used = new boolean[length];
        List<Integer> temp = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        f2(nums,used,temp,res);
        return res;
    }

    private void f2(int[] nums,boolean[] used,List<Integer> temp,List<List<Integer>> res) {
        if(temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i =0;i<nums.length;++i) {
            // 已经使用过
            if(used[i]) {
                continue;
            }
            used[i] = true;
            temp.add(nums[i]);
            f2(nums,used,temp,res);
            // 回溯
            temp.remove(temp.size()-1);
            used[i] = false;
        }
    }

    // 不使用标记数组
    // [0,first): 表示已经被填充过的元素 ==> 需要维护 [0,first)
    private void f1(int[] nums,List<Integer> temp ,List<List<Integer>> res,int first) {
        if(temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i = first;i<nums.length;++i) {
            temp.add(nums[i]);
            swap(nums,i,first);
            f1(nums,temp,res,first+1);
            temp.remove(temp.size()-1);
            swap(nums,i,first);
        }
    }

    private void swap(int[] nums,int left,int right) {
        int t= nums[left];
        nums[left] = nums[right];
        nums[right] = t;
    }

    /*
    * #problem 47 全排列 II
    * */
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        f(nums,used,res,temp);
        return res;
    }

    private void f(int[] nums,boolean[] used,List<List<Integer>> res , List<Integer> temp) {
        if(temp.size() == nums.length) {
            res.add(new ArrayList<>(temp));
            return ;
        }
        for(int i =0;i<nums.length;++i) {
            if(used[i]) {
                continue;
            }
            // i-1是未选过的元素 ==> 说明有重复的排列
            if(i>0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue;
            }
            temp.add(nums[i]);
            used[i] = true;
            f(nums, used, res, temp);
            used[i] =false;
            temp.remove(temp.size()-1);
        }

    }

}

/*
 * #problem 297 二叉树的序列化和反序列化
 * */
// 1. 利用层序遍历
class Codec {

    private Deque<TreeNode> queue = new LinkedList<>();


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return null;
        }
        queue.clear();
        queue.addLast(root);
        StringBuilder res = new StringBuilder();
        while(!queue.isEmpty()){
            int length = queue.size();
            for(int i =0;i<length;++i) {
                TreeNode cur = queue.removeFirst();
                if(cur == null) {
                    res.append("null,");
                } else {
                    res.append(cur.val);
                    res.append(",");
                }
                queue.addLast(cur.left);
                queue.addLast(cur.right);
            }
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null) {
            return null;
        }
        String[] split = data.split(",");
        queue.clear();
        int index = 0;
        TreeNode root = buildTreeNode(split[index++]);
        queue.addLast(root);
        while(!queue.isEmpty()) {
            int length = queue.size();
            for(int i =0;i<length;++i) {
                TreeNode cur = queue.removeFirst();
                TreeNode left = buildTreeNode(split[index++]);
                TreeNode right = buildTreeNode(split[index++]);
                cur.left = left;
                cur.right = right;
                if(left != null) {
                    queue.addLast(left);
                }
                if(right != null) {
                    queue.addLast(right);
                }
            }
        }
        return root;
    }

    private TreeNode buildTreeNode(String s) {
        if(s.equals("null")) {
            return null;
        }
        TreeNode node = new TreeNode();
        node.val = Integer.valueOf(s);
        return node;
    }
}
// 2. 深度搜索 --> 先序遍历
class Codec1 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "null,";
        }
        StringBuilder res = new StringBuilder();
        res.append(root.val);
        res.append(",");
        res.append(serialize(root.left));
        res.append(serialize(root.right));
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        List<String> datas = new LinkedList<>(Arrays.asList(split));
        return rDeserialize(datas);
    }

    private TreeNode rDeserialize(List<String> datas) {
        if(datas.get(0).equals("null")) {
            datas.remove(0);
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = Integer.valueOf(datas.get(0));
        datas.remove(0);
        root.left = rDeserialize(datas);
        root.right = rDeserialize(datas);
        return root;
    }
}
